﻿//1642. 可以到达的最远建筑
//给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
//你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
//当从建筑物 i 移动到建筑物 i + 1（下标 从 0 开始 ）时：
//如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
//如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或(h[i + 1] - h[i]) 个砖块
//如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。



class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders)
    {
        int n = heights.size();
        auto check = [&](int x)->bool
        {
            int b = bricks;
            priority_queue<int, vector<int>, greater<int>> min;
            for (int i = 0; i < x; i++)
            {
                if (heights[i + 1] > heights[i])
                    min.push(heights[i + 1] - heights[i]);
            }
            int num = min.size() - ladders;
            if (num <= 0)  return true;
            while (num--)
            {
                b -= min.top();
                min.pop();
            }
            return b >= 0;
        };

        int left = 0, right = heights.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (check(mid))
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left - 1;
    }
};